Fast Fourier transform (FFT) algorithms are computational tools that are widely used for calculating the discrete Fourier transform (DFT) of input data sequences. Most prior FFT algorithms focus on factoring the DFT matrix algebraically into sparse factors, thereby reducing the arithmetic cost associated with the DFT from an order N2 arithmetic cost, represented mathematically as O(N2), to an O(N log N) arithmetic cost, where N is the number of elements in the input data sequence. However, other types of costs, in addition to the arithmetic cost, can affect the performance of an FFT algorithm, especially in today's high-performance, distributed computing environments.
Wherever possible, the same reference numbers will be used throughout the drawing(s) and accompanying written description to refer to the same or like parts, elements, etc.